package sort.cmp;

/**
 * @Author: LDeng
 * @Date: 2021-03-24 15:20
 */
public class BinarySearch {

    //查找元素e在有序数组中的位置， 找不到返回-1
    public static int indexOf(Integer[] array,int e){
        if(array==null||array.length==0) return -1;
        int begin=0;
        int end=array.length;
        while(begin<end){
            int mid=(begin+end)>>1;//begin+end/2
            if(e<array[mid]){
                //新的查找范围[begin,mid]
                end=mid;
            }else if(e>array[mid]){
                //新的查找范围[mid+1,end)
                begin=mid+1;
            }else{
                return mid;
            }
        }
        return -1;//找不到
    }

    //查找e在有序数组array中待插入的位置
    //第一个大于e的位置
    public static int search(Integer[] array,int e){
        if(array==null||array.length==0) return -1;
        int begin=0;
        int end=array.length;
        while(begin<end){//循环退出的时候就是begin==end的时候
            int mid=(begin+end)>>1;
            if(e<array[mid]){
                //新的查找范围[begin,mid]
                end=mid;
            }
            if(e>=array[mid]){
                //新的查找范围[mid+1,end)
                begin=mid+1;
            }
        }
        //走到这里begin==end，返回位置即可
        return begin;
    }
}
